package algorithms.question.class01;

import common.util.MyUtil;

/**
 * 给定一个有序数组arr，代表坐落在X轴上的点
 * 给定一个正数K，代表绳子的长度
 * 返回绳子最多压中几个点？
 * 即使绳子边缘处盖住点也算盖住
 *
 * @author guichang
 * @date 2021/7/28
 */

@SuppressWarnings("all")
public class Code1_绳子盖住几个点 {

    public static void main(String[] args) {
        int[] arr = MyUtil.createArray(1, 2, 3, 4, 5, 6, 7, 8, 9);
        MyUtil.printf("盖住最多点：{}", maxPoint(arr, 1));

    }

    /**
     * 滑动窗口
     * 时间复杂度 O(N)
     */
    public static int maxPoint(int[] arr, int K) {
        if (arr == null || arr.length == 0 || K == 0) {
            return 0;
        }
        int N = arr.length;
        // 左右指针，从0开始
        int l = 0, r = 0;
        // 最多的点数
        int point = 0;
        while (l < N) {
            while (r < N && arr[r] - arr[l] <= K) {
                r++;
            }
            // r已经加1了，所以长度就是r-l
            point = Math.max(point, r - l++);
        }
        return point;
    }
}